package DataStructure.Tree;


/**
 * @Author：DijaH
 * @Date：2023/2/28 9:44 下午
 * @Version：1.0.0
 * @Description： 二叉树的最近公共祖先
 */
public class LowestCommonAncestor {

    public static class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(){}
        TreeNode(int val){this.val = val;}
        TreeNode(int val, TreeNode left, TreeNode right){
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public TreeNode lowest(TreeNode root,TreeNode p,TreeNode q){
        if(root == null){
            return null;
        }
        //base case
        if(root == p || root == q){
            return root;
        }

        TreeNode left = lowest(root.left,p,q);
        TreeNode right = lowest(root.right,p,q);

        //如果p和q都在以root为根的树中，那么left和right会走到base case
        if(left != null && right != null){
            return root;
        }
        //如果都不存在以root为根的树中
        if(left == null && right == null){
            return null;
        }
        //如果只有其中的一个存在以root为根的树中
        return  left == null ? right : left;
    }
}
